"""
read this topic，should use insert sort method,make this link list to two sections,

one section is in order, another section should sort,

we should get one node from the should sort to  in order link list in right position.
"""


class LinkNode:
    def __init__(self, val):
        self.val = val
        self.next = None

    def show(self):
        tmp = self
        res = []
        while tmp:
            if tmp.next:
                res.append(str(tmp.val))
                tmp = tmp.next
            else:
                res.append(str(tmp.val))
                tmp = None
        print('->'.join(res))


l1 = LinkNode(1)
l2 = LinkNode(2)
l3 = LinkNode(3)
l4 = LinkNode(4)
l4.next = l2
l2.next = l1
l1.next = l3


def insertion_sort_link_list(head):
    if head is None or head.next is None:
        return head
    # make link list to two sections
    # p it should be sort's head
    p = head.next
    # get head, so set head next  is None
    head.next = None
    # while p is not None
    while p:
        p_head = p.next  # p_head is record p.next position
        current = head  # current is head node
        if p.val <= head.val:  # if p.val less than head.val, p should be set to head
            p.next = head  # p.next is head
            head = p  # head is p
        # if insert position not in before head,should search
        else:
            # find in sorted link list, to find p should be set position
            # when current.next.val is less than p.val, current = current.next
            while current.next and current and current.next.val <= p.val:
                current = current.next
            # over the loop, p.val is less than current.next.val
            # p should set before current.next
            p.next = current.next  # so , p.next -> current.next
            current.next = p  # current.next -> p
        p = p_head  # p should set to p_head, is before we record p.next
    return head


l4.show()
result = insertion_sort_link_list(l4)
result.show()
